#ifndef _MyCountMinSketch_H
#define _MyCountMinSketch_H
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include "BOBHASH32.h"
#include "params.h"
#include "ssummary.h"
#include "BOBHASH64.h"
#include<queue>

#define CMS_d 4

using namespace std;


class MyCountMinSketch
{
private:
    int K, M2;
    BOBHash64* bobhash;
    ssummary* ss;
    int data[CMS_d][MAX_MEM + 10] = { 0 };


public:
    MyCountMinSketch(int M2, int K) :M2(M2), K(K)
    {
        ss = new ssummary(K); ss->clear();
        bobhash = new BOBHash64(1005);     
    }

    void clear()
    {
        ;
    }

    unsigned long long Hash(string ST)
    {
        return (bobhash->run(ST.c_str(), ST.size()));
    }

    void Insert(string x)
    {
        unsigned long long H = Hash(x);

        int min = 0xfffffff;

        for (int j = 0; j < CMS_d; j++)
        {
            int Hsh = H % (M2 - (2 * CMS_d) + 2 * j + 3);        // TODO: maybe should change this hash alg, but I don't know how to change
            data[j][Hsh] ++;
            if (data[j][Hsh] < min) {
                min = data[j][Hsh];
            }
        }

        int p = ss->find(x);
        // old flow that has been logged
        if (p) {
            int tmp = ss->Left[ss->sum[p]];
            ss->cut(p);
            if (ss->head[ss->sum[p]]) tmp = ss->sum[p];
            ss->sum[p] = min;
            ss->link(p, tmp);
        }
        // new flow
        else {
            if (min > (ss->getmin()) || ss->tot < K) {
                int i = ss->getid();
                ss->add2(ss->location(x), i);
                ss->str[i] = x;
                ss->sum[i] = min;
                ss->link(i, 0);
                while (ss->tot > K)
                {
                    int t = ss->Right[0];
                    int tmp = ss->head[t];
                    ss->cut(ss->head[t]);
                    ss->recycling(tmp);
                }
            }
        }
    }

    struct Node { string x; int y; } q[MAX_MEM + 10];
    static int cmp(Node i, Node j) { return i.y > j.y; }
    
    void work()
    {
        int CNT = 0;
        for (int i = N; i; i = ss->Left[i])
            for (int j = ss->head[i]; j; j = ss->Next[j]) {
                q[CNT].x = ss->str[j];
                q[CNT].y = ss->sum[j];
                CNT++;
            }
        sort(q, q + CNT, cmp);
    }

    pair<string, int> Query(int k)
    {
        return make_pair(q[k].x, q[k].y);
    }
};
#endif